package com.pan.alg.niuke.stackque;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 描述 请写一个整数计算器，支持加减乘三种运算和括号。
 *
 * <p>数据范围：0\le |s| \le 1000≤∣s∣≤100，保证计算结果始终在整型范围内
 *
 * <p>要求：空间复杂度： O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class ExpressionCalculate {

    public int solve (String s) {
        // write code here

        ArrayList<Integer> result = calculate(s,0);

        return result.get(0);
    }

    private ArrayList<Integer> calculate(String s, int index) {
        //操作数栈
        Stack<Integer> numStack = new Stack<>();
        char operation = '+';
        int num = 0;
        int i;
        //从第index个字符开始遍历
        for (i = index; i < s.length(); i++) {
            //
            char current = s.charAt(i);

            if(current>='0'&&current<='9'){
                num = num*10+ current - '0';
                if(i != s.length() - 1){
                    continue;
                }
            }

            if(current=='('){

                List<Integer> currentSList = calculate(s,i+1);
                num = currentSList.get(0);
                i = currentSList.get(1);

                if(i!=s.length()-1){
                    continue;
                }
            }

            switch(operation){
                //加减号先入栈
                case '+':
                    numStack.push(num);
                    break;
                case '-':
                    //相反数
                    numStack.push(-num);
                    break;
                //优先计算乘号
                case '*':
                    int temp = numStack.pop();
                    numStack.push(temp * num);
                    break;
            }

            num = 0;
            //右括号结束递归
            if(s.charAt(i) == ')'){
                break;
            } else{
                operation = current;
            }

        }

        int sum = 0;
        //栈中元素相加
        while(!numStack.isEmpty()){
            sum += numStack.pop();
        }

        ArrayList<Integer> temp = new ArrayList<>();
        temp.add(sum);
        temp.add(i);

        return temp;
    }

    public static void main(String[] args) {
        //
        String s = "((1+2)*5)+5";
        ExpressionCalculate expressionCalculate = new ExpressionCalculate();
        int solve = expressionCalculate.solve(s);
        System.out.println(solve);
    }
}
